//https://leetcode.cn/problems/even-odd-tree/

class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        if (root == nullptr)
            return true;

        queue<TreeNode*> q;
        int level = 0;
        int levelsize = 0;
        if (root)
        {
            q.push(root);
            levelsize = 1;
        }

        while (!q.empty())
        {
            int prev = level % 2 == 0 ? INT_MIN : INT_MAX;
            for (size_t i = 0; i < levelsize; i++)
            {
                TreeNode* front = q.front();
                q.pop();
                if (level % 2 == 0 && front->val % 2 == 0)
                {
                    return false;
                }
                if (level % 2 != 0 && front->val % 2 != 0)
                {
                    return false;
                }

                if ((level % 2 == 0 && front->val <= prev) || (level % 2 != 0 && front->val >= prev))
                    return false;
                prev = front->val;

                if (front->left)
                    q.push(front->left);
                if (front->right)
                    q.push(front->right);

            }
            levelsize = q.size();

            level++;

        }
        return true;
    }
};